n=1000;
p=373;
a=[811,762,-961,901,451,819,939,857,601,497,216,322,-17,497,-207,366,761,277,499,505,565,-401,505,-161,-362,717,-378,397,65,-573,-25,201,-787,375,871,356,751,-401,481,378,95,600,677,149,89,-433,-290,-681,221,569,-362,173,531,-586,-596,995,21,586,-481,-1,865,829,27,996,490,-4,523,445,-964,-537,801,577,641,765,9,701,386,773,-309,50,-546,891,-834,849,435,751,375,-73,-765,49,460,57,795,-777,833,-121,-366,669,561,549,-761,261,164,625,417,779,657,826,675,-785,543,471,553,-907,337,-348,-641,76,-101,937,567,141,301,-731,31,97,396,-471,354,984,319,593,923,95,797,701,-944,991,103,236,-725,857,-617,307,69,345,892,585,461,126,-949,353,817,465,825,206,889,535,-31,665,926,757,449,781,871,140,-813,-472,-741,279,309,-829,-721,975,-933,35,399,115,-721,489,-721,855,629,263,798,361,-211,751,831,-55,864,371,553,9,537,573,273,-121,-820,-97,341,921,-655,449,501,653,431,-13,884,-833,841,-794,652,40,213,-646,-753,-9,-665,885,445,57,-282,-161,-716,-421,-633,8,335,301,-297,967,829,300,393,-461,485,397,-265,-651,757,141,271,737,961,362,759,913,-931,-649,-677,457,-469,713,-183,-807,799,-513,-334,901,-557,65,409,577,243,989,851,153,551,-681,590,361,678,-411,100,-631,187,-351,167,251,326,884,265,411,881,448,-23,985,291,593,781,601,345,926,424,777,829,-441,-988,531,984,501,-750,802,939,-206,-253,-554,209,129,937,356,357,931,791,809,-145,491,-881,480,737,-739,718,-69,-361,998,631,832,649,754,709,656,853,349,916,819,137,789,-307,935,800,599,-539,293,139,206,888,320,741,723,704,-419,-413,601,-926,-630,945,601,572,-249,451,522,-449,825,-221,329,591,408,-265,-444,77,276,-688,146,-592,1,809,941,585,536,91,-1,145,331,-361,-17,486,229,171,-159,988,853,861,-601,-57,811,991,387,-755,17,611,697,763,-810,497,970,-13,809,-697,986,269,105,693,-976,-573,541,351,447,247,-506,881,717,378,81,577,595,738,265,701,950,-881,825,161,-697,-721,948,-1,-180,-273,-235,271,451,812,-850,-397,559,237,-153,-729,489,25,305,905,-761,997,687,341,671,-829,721,-224,-956,-410,751,-138,101,-383,857,-523,-863,789,-111,237,693,461,606,462,941,213,43,681,201,236,673,233,501,573,-139,755,473,281,-841,837,-745,577,413,-110,-487,824,-713,873,-88,931,89,209,575,49,357,-269,463,461,871,-65,-895,-136,-461,161,311,979,913,-761,135,289,955,701,281,209,993,-791,253,105,616,-1,250,301,-73,103,-326,-273,-571,624,554,-409,561,831,33,605,229,881,371,1,65,-420,891,-241,599,-831,-485,843,228,797,660,849,-489,225,-351,-641,505,-451,-989,-893,673,541,165,926,564,189,141,411,76,-741,-176,924,853,-557,459,839,611,579,-777,-651,987,641,353,-361,636,-385,993,321,681,311,-147,827,247,849,206,801,492,174,888,221,699,191,673,388,-641,-61,161,569,-425,301,265,585,697,201,665,554,524,-11,-605,183,729,461,588,281,-889,126,-561,601,805,-41,-282,387,-29,943,-633,-425,907,35,917,373,-501,972,-769,-841,-649,801,-929,-946,849,-521,843,60,-913,217,428,-38,193,-121,-1,621,44,133,26,513,-926,939,931,945,-473,169,546,753,721,531,-709,589,-242,203,-333,-353,-1,121,113,-519,674,521,251,-343,136,711,-877,242,411,-891,-42,196,761,-127,231,217,-405,673,451,831,33,-195,416,281,-231,841,-806,521,371,318,195,-433,-121,71,388,141,777,301,89,653,357,656,-601,545,783,-450,187,941,131,775,-432,265,823,769,105,545,-526,-293,-697,65,517,-927,441,-601,129,95,905,797,-877,636,571,-314,-501,-517,321,189,241,-749,-88,715,-196,784,503,71,611,870,-566,-459,631,555,-947,691,341,119,235,895,493,-425,99,844,921,50,345,589,517,-263,148,957,161,457,-521,-876,923,-428,-505,-216,631,717,-421,351,217,-586,-473,359,466,-369,149,-599,85,-186,177,-1,81,-501,-317,-733,659,885,-346,705,415,13,1,417,259,69,-353,851,237,531,481,270,427,-9,781,366,705,421,-692,299,883,510,899,-405,737,-241,-683,-791,489,665,411,542,307,206,16,-388,771,26,109,951,-624,461,522,101,101,285,-617,-551,-476,831,360,823,709,-57,376,537,101,705,-385,-493,605,-239,-59,893,611,-881,634,953,881,-801,-111,796,701,-11,180,570,506,81,897,121,-525,169,231,78,389,-521,-801,-599,569,803,-921,-487,429,455,-953,229,273,611,271,-961,-347,915,318,-26,-954,881,697,-596,511,841,962,-913,56,803,527,783,4,177,-698,626,601,-901,617,89,-857,678,75,847,-806,474,926,802,440,1,646,466,617,337,-785,111,-569,361,611,297,629,-49,753,182,321,-81,-759,881,457,425,885,181,809,321,961,64,461,52,48,201,478];